from collections import deque
from tools.listNode import listToNode


def isPalindrome(root):
    if not root:
        return True
    q = deque()
    while root:
        q.append(root.val)
        root = root.next
    while len(q) > 1:
        if q.pop() != q.popleft():
            return False
    return True


print(isPalindrome(listToNode([1, 2, 3])))
print(isPalindrome(listToNode([1, 2, 2, 1])))
print(isPalindrome(listToNode([1, 2, 1])))
